package tianhao.luo.algorithm;

/**
 * 选择排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  8:59
 */
public class SelectSort {

    private int[] array;

    public SelectSort(int[] array) {
        this.array = array;
    }


    /**
     * 选择排序:就是每一轮扫描出(选择出)最小元素,和起始位置元素进行交换
     * 嵌套for循环,它的时间复杂度为O(n^2)
     *
     *
     * 思路:
     * 1. 从第一个位置开始,假定array[0]就是最小的,利用一个临时的变量index来存储最小元素的索引
     * 2. 向后扫描,发现有元素的值小于array[index],就把该元素的索引更新到临时变量index;直到扫描到数组结尾
     * 3. 第一轮扫描完毕后,将临时变量index索引位置的元素和开始的索引位置元素array[0]进行交换
     * 4. 开始下一轮,不过是从上一轮默认最小节点的下一个节点开始扫描.即从array[1]开始向后扫描
     * 5. 依次遍历......直到轮次等于array.length-2,它表示本轮次默认最小的节点位置就是在数组最后一个元素的前一位
     * 6. 再执行一次扫描比较,就表示排序完毕了
     */
    public void sort(){
        // 每一轮扫描起始位置的索引是随轮次变化的,而我们假定的最小元素的索引index,也是和轮次有关的,值为轮次-1,即j;
        // 因为是从本位置开始和后一个元素相比较的,那么它只需要扫描到索引等于array.length-2位置即可,后面元素的比较是交给作比较交换的循环的.
        // 开始作比较的是index元素的后一位,那么i的值就是index+1,即j+1;并且会扫描到数组结尾,即控制循环的的条件为小于array.length
        for (int j = 0; j < array.length - 1; j++) {
            // 每一轮完毕,总是会找到最小的元素放置在我们假定的起始位置
            // 例如:第一轮,找出与后面相比的最小元素放在数组第一个位置
            // 第二轮,从数组第二个元素开始,找出与后面相比的最小元素放在数组第二个位置
            // .......
            // 所以我们可以假定每一轮的起始位置就是轮次,对于数组的索引就是轮次-1,即j
            int index=j;
            for (int i = j+1; i < array.length; i++) {
                if (array[i]<array[index]){
                    index =i;
                }
            }
            // 确定了最小位置的索引了,开始交换元素
            // 需要注意,如果扫描完后,j就是最小的,那么就不需要进行交换了
            if (index !=j){
                int temp=array[j];
                array[j] = array[index];
                array[index] = temp;
            }
        }
    }
    /**
     * 打印
     */
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }
}
